package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 1937. 扣分后的最大得分
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/28 17:20
 */
public class MaxPoints1937 {

    public static void main(String[] args) {
        MaxPoints1937 test = new MaxPoints1937();

        // 9
//        int[][] points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};

        // 11
        int[][] points = {{1, 5}, {2, 3}, {4, 2}};

        long l = test.maxPoints(points);
        System.out.println(l);
    }


    public long maxPoints(int[][] points) {
        int m = points.length;
        int n = points[0].length;
        long[] arr = new long[n];
        long[] values = new long[n];
        int[] one = points[0];
        for (int i = 0; i < n; i++) {
            values[i] = one[i];
        }
        for (int i = 1; i < m; i++) {
            int[] items = points[i];
            long max = values[0];
            for (int j = 0; j < n; j++) {
                max = Math.max(values[j], max - 1);
                arr[j] = max;
            }
            max = values[n - 1];
            for (int j = n - 1; j >= 0; j--) {
                max = Math.max(max - 1, values[j]);
                values[j] = items[j] + Math.max(max, arr[j]);
            }
        }
        long max = 0;
        for (long item : values) {
            max = Math.max(max, item);
        }
        return max;
    }

}
